{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  排列（Permutation）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **定义**：从 $n$ 个不同元素中选取 $r$ 个，并按照一定顺序排列，得到的有序序列称为一个排列。\n",
    "\n",
    "- **公式**：$P(n, r) = \\frac{n!}{(n-r)!}$, 其中 $n!$ 表示 $n$ 的阶乘，即 $n \\times (n-1) \\times \\dots \\times 1$。\n",
    "\n",
    "- **简单例子**：从 $\\{1, 2, 3\\}$ 中选取 2 个元素排列。\n",
    "  - 所有可能的排列：$(1,2), (2,1), (1,3), (3,1), (2,3), (3,2)$ 共 6 个。\n",
    "  - 计算：$P(3, 2) = \\frac{3!}{(3-2)!} = \\frac{6}{1} = 6$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "全排列的总数为：$n! = n \\times (n-1) \\times (n-2) \\times \\cdots \\times 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "全排列 (`std::next_permutation` / `std::prev_permutation`)\n",
    "- `std::next_permutation` 会将给定序列重新排列成下一种字典序（lexicographical order）；若已是最后一种排列，则会返回 `false` 并将序列重置为最小排列（升序排序）。\n",
    "\n",
    "**要点：**\n",
    "\n",
    "- 初始序列需为字典序最小排列（升序）。\n",
    "- 时间复杂度为 `O(n)` 生成下一个排列。\n",
    "- 配合 `std::prev_permutation` 可以从最大排列向前生成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 \n",
      "1 3 2 \n",
      "2 1 3 \n",
      "2 3 1 \n",
      "3 1 2 \n",
      "3 2 1 \n"
     ]
    }
   ],
   "source": [
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <vector>\n",
    "\n",
    "{\n",
    "    // 待排列的序列\n",
    "    std::vector<int> nums = {1, 2, 3};\n",
    "\n",
    "    // 在使用 std::next_permutation 之前，必须先将序列排序为字典序最小状态\n",
    "    // 这样才能从最小排列开始，依次生成字典序逐渐增大的排列\n",
    "    std::sort(nums.begin(), nums.end());\n",
    "\n",
    "    // 使用 do-while 循环，确保初始排列也被处理和输出\n",
    "    do {\n",
    "        // 输出当前排列\n",
    "        for (int x : nums) {\n",
    "            std::cout << x << ' ';\n",
    "        }\n",
    "        std::cout << '\\n';\n",
    "\n",
    "        // std::next_permutation 会尝试将序列 rearrange 成字典序下一个排列\n",
    "        // 若成功，返回 true；若当前已经是字典序最大排列，则返回 false，循环结束\n",
    "    } while (std::next_permutation(nums.begin(), nums.end()));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/Knv3n5aPW\n",
    "// C++20 的 `<ranges>` 库提供了 `std::ranges::next_permutation` 等算法，有更严格的概念约束和更好的可读性：\n",
    "\n",
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <ranges>\n",
    "#include <vector>\n",
    "\n",
    "int main() {\n",
    "    std::vector<int> nums = {1, 2, 3};\n",
    "    std::ranges::sort(nums);\n",
    "\n",
    "    do {\n",
    "        for (int x : nums) std::cout << x << ' ';\n",
    "        std::cout << '\\n';\n",
    "    } while (std::ranges::next_permutation(nums).found);\n",
    "\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 组合（Combination）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **定义**：从 $n$ 个不同元素中选取 $r$ 个，不考虑顺序的集合称为一个组合。\n",
    "\n",
    "- **公式**：\n",
    "\n",
    "  $C(n, r) = \\binom{n}{r} = \\frac{n!}{r! (n-r)!}$\n",
    "\n",
    "- **简单例子**：从 $\\{1, 2, 3\\}$ 中选取 2 个元素组合。\n",
    "\n",
    "  - 所有可能的组合：$\\{1,2\\}, \\{1,3\\}, \\{2,3\\}$ 共 3 个。\n",
    "  - 计算：$C(3, 2) = \\frac{3!}{2! \\cdot 1!} = \\frac{6}{2} = 3$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "生成组合（利用排列思想）\n",
    "- STL 没有直接的组合函数，但可以通过“二进制掩码 + `next_permutation`”实现，例如求从 `n` 个元素中选取 `k` 个元素的所有组合\n",
    "\n",
    "**要点：**\n",
    "\n",
    "- 使用二进制掩码（`1` 表示选中，`0` 表示未选中）。\n",
    "- 可以使用 `next_permutation` 或 `prev_permutation`，取决于掩码的初始排列。\n",
    "- 总复杂度约为 `O(C(n, k) * n)`，因为总共有组合数 `C(n, k)` 个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 \n",
      "1 3 \n",
      "1 4 \n",
      "2 3 \n",
      "2 4 \n",
      "3 4 \n"
     ]
    }
   ],
   "source": [
    "// TODO: ?\n",
    "// 用一个由 1 和 0 组成的掩码（mask）来表示组合的选择状态，再配合 std::prev_permutation 来枚举所有不同的掩码排列，从而生成所有的组合\n",
    "\n",
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <vector>\n",
    "\n",
    "{\n",
    "    // 原始数字序列，表示我们要从中挑选元素的集合\n",
    "    std::vector<int> nums = {1, 2, 3, 4};\n",
    "    int k = 2;                    // 每个组合要选取的元素个数\n",
    "    int n = nums.size();          // 数组总长度，便于后续使用\n",
    "\n",
    "    // 掩码（mask）用于记录“哪些位置被选中”。\n",
    "    // 先放入 k 个 1，表示初始时选择前 k 个位置。\n",
    "    std::vector<int> mask(k, 1);\n",
    "\n",
    "    // 将掩码扩展为长度 n，缺的部分用 0 填充。\n",
    "    // 最终得到的 mask 为 [1, 1, 0, 0]，即初始选择 nums 的前两个元素。\n",
    "    mask.resize(n, 0);\n",
    "\n",
    "    // 用于保存所有组合的二维向量\n",
    "    std::vector<std::vector<int>> combinations;\n",
    "\n",
    "    // do-while 循环确保初始掩码状态也会被处理一次\n",
    "    do {\n",
    "        // 临时向量存放当前掩码对应的组合\n",
    "        std::vector<int> comb;\n",
    "\n",
    "        // 遍历掩码的每一位\n",
    "        for (int i = 0; i < n; ++i) {\n",
    "            // 当掩码的当前位是 1 时，说明 nums[i] 被选中\n",
    "            if (mask[i]) {\n",
    "                comb.push_back(nums[i]);\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 将当前组合放入结果集中\n",
    "        combinations.push_back(comb);\n",
    "\n",
    "        // 利用 std::prev_permutation 生成下一种掩码排列（字典序更小的排列）\n",
    "        // 当无法再生成新的排列时，函数返回 false，循环结束\n",
    "    } while (std::prev_permutation(mask.begin(), mask.end()));\n",
    "\n",
    "    // 遍历并输出所有组合，每行一个组合，元素之间用空格分隔\n",
    "    for (const auto& comb : combinations) {\n",
    "        for (int x : comb) {\n",
    "            std::cout << x << ' ';\n",
    "        }\n",
    "        std::cout << '\\n';\n",
    "    }\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
